/**
 * Copyright (c) 2009 Koder Chen. All Rights Reserved.
 *
 * bigint.h
 * The file defines the basic operations needed to manipulate the big integer,
 * including the add, minus, multiply, and so, on
 *
 *  Author: chenfuhan
 * Created: 2009-6-1
 * Version: 1.0
 */
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <assert.h>

#include "bigint.h"
#include "tool.h"
#include "rsa.h"

i32_t MAX_BITS = 64;
i32_t MAX_BYTES = 8;

u8_pt bi_mod_t = NULL;
u8_pt bi_mul_t = NULL;
u8_pt bi_div_pt = NULL;
u8_pt bi_div_qt = NULL;

// constants for common used
const u32_t BITS[9]={0, 1, 3, 7, 15, 31, 63, 127, 255};

void bi_add(u8_pt a, u8_pt b, u8_pt out)
{
	// assert for debug
	assert(a && b && out);
	// the calculation
	u32_t i=0, c=0, m=0;
	u8_pt t=rsa_default_malloc();
	for(i=0;i<MAX_BYTES;i++)
	{
		m=a[i]+b[i]+c;
		c=(m >> 8);
		t[i]=(m & 0xff);
	}
	// we does not do with the overflow occasion, and we assume that
	// the overflow will be consumed by before reach the MAX_BYTES
	bi_copy_bytes(out, t, 0, MAX_BYTES);
	rsa_free(t);
}

void bi_sub(u8_pt a, u8_pt b, u8_pt out)
{
	// assert for debug
	assert(a && b && out && bi_comp(a, b)>=0);
	// the calculation
	i32_t i=0, c=0, m=0;
	u8_pt t=rsa_default_malloc();
	for(i=0;i<MAX_BYTES;i++)
	{
		m=a[i]-b[i]-c;
		if(m<0)
		{
			t[i]=m+256;
			c=1;
		}
		else
		{
			c=0;
			t[i]=m;
		}
	}
	bi_copy_bytes(out, t, 0, MAX_BYTES);
	rsa_free(t);
}

void bi_mul(u8_pt a, u8_pt b, u8_pt out)
{
	// assert for debug
	assert(a && b && out);
	// calculation
	i32_t i=0, j=0, c=0, r=0, k=0;
	memset(bi_mul_t, 0, 2 * MAX_BYTES);

	//i32_t abytes = bi_bytes(a);
	//i32_t bbytes = bi_bytes(b);

	//printf("bytes %d %d\n", abytes, bbytes);
	//fflush(stdout);

	for(i=0;i<MAX_BYTES;i++)
	{
		for(c=0, j=0;j<MAX_BYTES;j++)
		{
			r=i+j;
			k=bi_mul_t[r]+(a[i]*b[j]+c);
			c=(k>>8);
			bi_mul_t[r]=(k & 0xff);
		}
	}
	//if(c != 0) bi_mul_t[r] = c;
	// we only pay attention to the low MAX_BYTES data, the overflow
	// part will be treated just as 'overflow'
	bi_copy_bytes(out, bi_mul_t, 0, MAX_BYTES);
}

void bi_div(u8_pt a, u8_pt b, u8_pt quot, u8_pt rema)
{
	// assert for debug
	assert(a && b && quot && rema);
	// the calculation
	i32_t abits=0, bbits=0, i=0, c=0;
	// check the number of realbytes, and make sure we are not
	// divided by zero
	abits=bi_bits(a);
	bbits=bi_bits(b);
	// assertion for debug
	assert(bbits!=0);
	// the calculation
	if(bi_comp(a, b)<0)
	{
		bi_reset(quot);
		bi_copy_bytes(rema, a, 0, MAX_BYTES);
	}
	else
	{
		bi_reset(bi_div_pt);
		bi_reset(bi_div_qt);
		// copy the part of product
		bi_copy_bits(bi_div_pt, a, abits-bbits+1, bbits-1);
		// now the calculation
		for(c=bbits-1, i=abits-bbits;i>=0;i--)
		{
			bi_lshift(bi_div_pt, 1);
			bi_set_bit(bi_div_pt, 0, bi_get_bit(a, i));
			if(c>=(bbits-1) && bi_comp(bi_div_pt, b)>=0)
			{
				bi_set_bit(bi_div_qt, i, 1);
				bi_sub(bi_div_pt, b, bi_div_pt);
				c=bi_bits(bi_div_pt);
			}
			else
			{
				bi_set_bit(bi_div_qt, i, 0);
				c++;
			}			
		}
		// fetch the quotient
		bi_copy_bytes(quot, bi_div_qt, 0, MAX_BYTES);
		// fetch the remainder
		bi_copy_bytes(rema, bi_div_pt, 0, MAX_BYTES);
	}
}

void bi_mod(u8_pt a, u8_pt b, u8_pt out)
{
	bi_div(a, b, bi_mod_t, out);
}

void bi_gcd(u8_pt a, u8_pt b, u8_pt out)
{
	u8_pt p = rsa_default_malloc();
	u8_pt q = rsa_default_malloc();
	u8_pt r = rsa_default_malloc();
	u8_pt t = 0;
	// initialization
	bi_copy_bytes(p, a, 0, MAX_BYTES);
	bi_copy_bytes(q, b, 0, MAX_BYTES);
	// make sure p is bigger than q
	if(bi_comp(p, q) < 0)
	{
		u8_pt t = p;
		p = q;
		q = t;
		t = 0;
	}
	while(bi_bits(q) > 0)
	{
		t = p;
		bi_mod(p, q, r);
		p = q;
		q = r;
		r = t;
		t = 0;
	}

	bi_copy_bytes(out, p, 0, MAX_BYTES);
	rsa_free(p);
	rsa_free(q);
	rsa_free(r);
}

void bi_powm(u8_pt a, u8_pt b, u8_pt n, u8_pt out)
{
	u8_pt r = rsa_default_malloc();
	u8_pt m = rsa_default_malloc();
	bi_mod(a, n, r);
	i32_t bits = bi_bits(b)-2;
	while(bits >= 0)
	{
		i32_t t = bi_get_bit(b, bits);
		if (t == 0)
		{
			bi_mul(r, r, r);
			bi_mod(r, n, r);
		}
		else
		{
			bi_mul(r, r, r);
			bi_mod(r, n, r);
			bi_mul(r, a, r);
			bi_mod(r, n, r);
		}
		bits --;
	}
	bi_copy_bytes(out, r, 0, MAX_BYTES);
	rsa_free(r);
	rsa_free(m);
}

void bi_copy_bytes(u8_pt dst, u8_pt src, i32_t start, i32_t bytes)
{
	// assert for debug
	assert(dst && src && bytes>=0 && start>=0 && (bytes+start)<=MAX_BYTES);
	// calculation
	if(dst != src)
	{
		i32_t i=0;
		bi_reset(dst);
		for(i=0;i<bytes;i++)
		{
			dst[i]=src[start+i];
		}
	}
}

void bi_copy_bits(u8_pt dst, u8_pt src, i32_t start, i32_t bits)
{
	// assert for debug
	assert(dst && src && bits>=0 && start>=0 && (bits+start)<=MAX_BITS);
	if(dst != src)
	{
		// now begin with the normal calculation
		bi_reset(dst);
		i32_t i=0, bytes=(bits+7)/8, rema=bits%8;
		// allocate the external space for temparary usage
		u8_pt t=rsa_default_malloc();
		bi_copy_bytes(t, src, 0, MAX_BYTES);
		// use the right shift to help the job
		bi_rshift(t, start);
		// and then, just copy the first 'bytes' byte of the temparary holder
		for(i=0;i<bytes;i++)
		{
			dst[i]=t[i];
		}
		// check whether there is a mistake, and correct it
		if(rema!=0) 
			dst[bytes-1]=(t[bytes-1]&BITS[rema]);
		// free the space
		rsa_free(t);
	}
}

void bi_set_bit(u8_pt a, i32_t pos, i32_t v)
{
	// assert for debug
	assert(a && pos>=0 && pos<MAX_BITS);
	// calculation
	//i32_t bytes=pos/8, curr=pos%8, i=1<<curr;
	i32_t bytes=(pos >> 3), curr=(pos & 7), i=(1<<curr);
	u8_t  t=(i ^ 255);
	a[bytes]=(v==0?(a[bytes] & t):(a[bytes] | i));
}

i32_t bi_get_bit(u8_pt a, i32_t pos)
{
	// assert for debug
	assert(a && pos>=0 && pos<MAX_BITS);
	// calculation
	i32_t bytes=pos/8, curr=pos%8;
	return (a[bytes] >> curr) & 1;
}

i32_t bi_bits(u8_pt a)
{
	// assert for debug
	assert(a);
	// calculation
	i32_t i=MAX_BYTES-1, j=0;
	while(i>=0 && a[i]==0){i--;}
	if(i<0)
	{
		return 0;
	}
	for(j=7;j>=0 ;j--)
	{
		if(a[i] & (1<<j)) break;
	}
	return ((i<<3)+j+1);
}
 
i32_t bi_comp(u8_pt a, u8_pt b)
{
	// assert for debug
	assert(a && b);
	// calculation
	i32_t i=0;
	for(i=MAX_BYTES-1;i>=0;i--)
	{
	 if(a[i]>b[i]) return 1;
	 else if(a[i]<b[i]) return -1;
	}
	return 0;
}
 
void bi_reset(u8_pt a)
{
	assert(a);
	if(a)
	{
		memset(a, 0, MAX_BYTES);
	}
} 

void bi_lshift(u8_pt a, i32_t bits)
{
	// assert for debug
	assert(a && bits>=0 && bits<=MAX_BITS);
	// shift operation
	i32_t i=0;
	for(i=MAX_BITS-1;i>=bits;i--)
		bi_set_bit(a, i, bi_get_bit(a, i-bits));
	for(i=0;i<bits;i++) 
		bi_set_bit(a, i, 0);
}
 
void bi_rshift(u8_pt a, i32_t bits)
{
	// assert for debug
	assert(a && bits>=0 && bits<=MAX_BITS);
	// shift operation
	i32_t i=0;
	for(i=0;i<MAX_BITS-bits;i++)
		bi_set_bit(a, i, bi_get_bit(a, i+bits));
	for(i=MAX_BITS-1;i>=MAX_BITS-bits;i--)
		bi_set_bit(a, i, 0);
}

i32_t bi_bytes(u8_pt a)
{
	i32_t retv = MAX_BYTES - 1;
	while(retv >= 0 && a[retv] == 0) retv --;
	return retv + 1;
}
